package a_doubleWrite;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;

/**
 * 最小覆盖子串（滑动窗口）
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-08-02 09:40
 */
public class L76 {
    public String minWindow(String s, String t) {
        if (t.length() > s.length()) return "";
        int left = 0;//窗口左边界
        int right = 0;//窗口右边界
        int start = 0;//满足条件开始
        int maxLen = Integer.MAX_VALUE;//初始化最大包含长度
        //保存t,出现个数
        Map<Character, Integer> map1 = new HashMap<>();
        for (char c : t.toCharArray()) {
            map1.put(c, map1.getOrDefault(c, 0) + 1);
        }
        //
        while (right < s.length()) {
            char c = s.charAt(right);
            if (map1.containsKey(c)) {
                map1.put(c, map1.get(c) - 1);
            }
            right++;//右边界++
            //如果窗口中包含了t
            while (check(map1)) {
                //如果更短记录
                if (right - left < maxLen) {
                    maxLen = right - left;
                    start = left;
                }
                //左边界向右移1，再判断
                char c1 = s.charAt(left);
                //map中c1+1
                if (map1.containsKey(c1)) {
                    map1.put(c1, map1.get(c1) + 1);
                }
                left++;
            }
        }

        if (maxLen != Integer.MAX_VALUE) {
            return s.substring(start, start + maxLen);
        }
        return "";
    }

    //判断是否可以
    public boolean check(Map<Character, Integer> map) {
        for (int i : map.values()) {
            if (i > 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        L76 l76 = new L76();
        String s = l76.minWindow("acbbaca",
                "aba");
        System.out.println(s);
    }
}
